package code.c02_list.sqList;

import code.c02_list.sqList.SqListClass;

/**
 * @author thinkpad - 83start
 * @version v1.0
 * @create 2022/9/11 20:42
 * @package code.c02_list.classwork.examples
 * @description 一个长度为L（L≥1）的升序序列S，处在第 L/2 个位置的数称为S的中位数。
 * 例如：若序列S1 = (11,13,15,17,19),则S1 的中位数为15。
 * 两个序列的中位数是包含他们所有的元素的升序序列的中位数。
 * 例如：若序列S2 = (2,4,6,8,20),则S1 和 S2 的中位数是 11。
 * 现有连个等长的升序序列 a 和 b ，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列数组的中位数。
 */

public class Exam_2_7 {
    public static int findMedianNum(SqListClass<Integer> a, SqListClass<Integer> b) {
        SqListClass<Integer> c = new SqListClass<>();
        int i = 0;
        int j = 0;
        while (i < a.size() && j < b.size()) {
            if (a.getElem(i) < b.getElem(j)) {
                c.add(a.getElem(i));
                i++;
            } else {
                c.add(b.getElem(j));
                j++;
            }
        }

        // 如果a没有遍历完毕
        while (i < a.size()){
            c.add(a.getElem(i ++));
        }

        // 如果b没有遍历完毕
        while (j < b.size()){
            c.add(b.getElem(j++));
        }

        System.out.println(c.toString());

        int middlei = c.size / 2;
        return c.getElem(middlei);
    }

    public static void main(String[] args) {

        Integer[] aArr = {11, 13, 15, 17, 19};
        Integer[] bArr = {2, 4, 6, 8, 20};

        SqListClass<Integer> a = new SqListClass<>();
        a.createList(aArr);

        SqListClass<Integer> b = new SqListClass<>();
        b.createList(bArr);

        System.out.println(findMedianNum(a, b));
    }
}
